這題要算擁有 n 個節點的唯一二元搜索樹結構數量，根據 BST 的特性，左子樹中的所有節點都小於根節點，右子樹中的所有節點都大於根節點，所以可以用動態規劃來解決這題。

分析：
首知道每個節點都可以當根節點，假設對 n 個節點，每節點都可以是根節點，這樣左子樹的節點數量是 i - 1（節點 i 是根），右子樹的節點數是 n - i，左子樹和右子樹的組合數量相乘就是以 i 為根節點的所有可能 BST 數量，所以可以用遞迴或者動態規劃來算整體樹數量。
公式：
G(n)=∑
i=1
n
G(i−1)×G(n−i)

G(n) 是 n 個節點時的唯一 BST 數量
G(0)=1，空樹也算一種 BST
G(1)=1，只有一個節點，只有一種 BST
步驟：
確認狀態跟遞迴公式，要算 n 個節點的 BST 數量，這可以透過把每個節點設為根節點來算，初始條件，定義 G(0)=1 和 G(1)=1 當成基礎情況，動態規劃計算，用一個數組儲存每個節點數量下的結果，再從小到大逐步累加，最後得到 𝐺(𝑛)。
程式碼：
class Solution(object):
def numTrees(self, n):
"""
:type n: int
:rtype: int
"""
#初始化動態規劃陣列，dp[i] 表 i 個節點的唯一 BST 數量
dp = [0] * (n + 1)

    #基礎條件：空樹（0個節點）和一個節點的樹都有唯一的形狀
    dp[0] = 1
    dp[1] = 1
    
    #從 2 到 n 算每個節點數量下的 BST 結構
    for i in range(2, n + 1):
        # 對每個節點數量 i，選 j 當根節點
        for j in range(1, i + 1):
            # 左子樹的節點數是 j-1，右子樹的節點數是 i-j
            dp[i] += dp[j - 1] * dp[i - j]
    
    #返回 dp[n]，就是 n 個節點時的唯一 BST 數量
    return dp[n]

解釋：
動態規劃陣列初始化，dp 陣列的大小是 n + 1，且初始化所有元素為 0，dp[i] 表當有 i 個節點，可以形成的唯一 BST 的數量，基礎條件，設 dp[0] = 1 和 dp[1] = 1，表空樹和只有一個節點的樹都有唯一的結構，遞迴關係，對每個節點數量 i，算可能的 BST 結構數，根據公式，把每個節點當根節點時的左子樹和右子樹的數量相乘，再把結果累加到 dp[i] 中，最後結果，返回 dp[n]，這就是有 n 個節點的所有唯一 BST 結構的總數，這個解法通過動態規劃，打計算的複雜度降低到 O(n 的2次方）因為對每個 i 要遍歷 1 到 i，所以有兩層迴圈。
心得：
透過動態規劃解決，可以提升效率，相比遞迴方法來說，不會重複計算導致時間拉長，學這題讓我對動態規劃操做的理解更多，尤其是處理遞迴關係時，怎麼通過儲中間結果來減少重複運算。